package 回溯;
import java.util.HashMap;
import java.util.LinkedList;
/*
 * 全排列的 问题  你写的 只能 是 区间 （区间 是连续的 ） 而 子集  是随便挑的啊 
 */
public class leetcode1994好子集的题目 {
	public static void main(String []args) {
		int nums[] = {4,2,3,15};
		LinkedList<Integer> path =new LinkedList<>();
//		process(0,nums,false);
		process(nums,0,path);
		System.out.println(ways);
	}
	
	
	public static void process(int nums[],int index,LinkedList<Integer> path) {
//		System.out.println(path);
		if(judge(path)) {
			ways++;
			System.out.println(path);
		}
		for(int i = index;i < nums.length;i++) {
			path.add(nums[i]);
			process(nums,i+1,path);
			path.removeLast();
		}
			
	}
	
	public static boolean judge(LinkedList<Integer> path) {
		HashMap<Integer,Integer> map =new HashMap<>();
		
		int []	primeNum = {2,3,5,7,11,13,17,19,23,29};
		for(int i : primeNum) {
			map.put(i, 1);
		}
		int temp1=1;
		int temp2=1;
//		for(int i = start; i<= end;i++) {
//			temp1 *= nums[i];
//		}
		for(int value : path) {
			temp1*=value;
		}
		if(temp1 == 1) {
			return false;
		}
		if(map.containsKey(temp1)) {
			return  true;
		}
		for(int value : primeNum) {
			temp2*=value;
			if(temp1==temp2) {
				return true;
			}
		}
		return false;
}
 //	public static int process(int index,int [] nums,boolean flag) {
//		//basecase how to write         count++  就是count=count+1;
//		if(flag) {
//			return 1;
//		}
//		int ways=0;
//		for(int i = index; i < nums.length;i++) {
//			ways+=process(i+1,nums,judge(index,i,nums));
//		}
//		
//		return ways;
//	}
	static	int ways=0;
	public static void process(int index,int [] nums,boolean flag) {
		//basecase how to write         count++  就是count=count+1;
		if(flag) {
			ways++;
		}
//		int ways=0;
		for(int i = index; i < nums.length;i++) {
			process(i+1,nums,judge(index,i,nums));
		}
		
//		return ways;
	}
	public static boolean judge(int start,int end,int nums[]) {
			int []	primeNum = {2,3,5,7,11,13,17,19,23,29};
			int temp1=1;
			int temp2=1;
			for(int i = start; i<= end;i++) {
				temp1 *= nums[i];
			}
			if(temp1 == 1) {
				return false;
			}
			for(int value : primeNum) {
				temp2*=value;
				if(temp1==temp2) {
					return true;
				}
			}
			return false;
	}
}
